package com.atguigu.kmp;

import java.util.Arrays;

public class SearchStringDemo {
    public static void main(String[] args) {
        String content="ABC ABDD ABCDABD";
        String key="ABCDABD";

        // "ABACDABAC"
        int[] matchArr = matchArr2("ABCABA");
        System.out.println(Arrays.toString(matchArr));

//        int search = search(content, key);
//        System.out.println(search);
    }

    public static int search(String content,String key){
        int cindex=0;
        int kindex=0;
        int[] matchArr = matchArr2(key);

        boolean startCompare=false;
        while(cindex<content.length()&&kindex<key.length()){
            if(content.charAt(cindex)==key.charAt(kindex)){
                startCompare=true;
                kindex++;
            }else if(startCompare){
                startCompare=false;
                cindex=cindex-matchArr[kindex];
                kindex=0;
            }

            cindex++;
        }


        return kindex==key.length()?cindex-kindex:-1;
    }


    /**
     * 优化后的匹配值(前缀长度)记录
     * 利用了一个特性:后面下标的匹配值, 要么是前面下标的匹配值+1, 要么是0, 要么是1
     * 0: 未匹配上. 两种情况:1)前面连续的情况被中断;2)与首字符也不相等;
     * 1: 匹配上首字符. 与0的情况相似, 前面连续的情况一定中断或一直未连上
     * prev+1: 匹配上后继字符.
     *
     * 如果当前字符的匹配值>=2, 则说明当前字符至少是一个长度>=2的前缀的最后一个字符. 则该字符的前字符, 必定也在该前缀内, 其匹配值必定>=1
     * 换个角度讲, 如果前面的字符的匹配值>0, 由匹配值可推测出具体是哪个前缀(匹配值=前缀长度), 与当前字符合并, 可判断是否可延续为新的长度+1的前缀
     * 如果不行, 则仅需考虑0和1的情况
     *
     * @param key
     * @return
     */
    public static int[] matchArr2(String key){
        int[] matchArr=new int[key.length()];

        // 已经构建的匹配字符串大小
        int pos=0;
        for(int i=1;i<key.length();i++){
            if(pos>0){
                // 如果post>0, 则比较当前字符与pos下标的字符是否相等
                // 相等, 则pos++, 并将当前下标的匹配值设置为新的pos
                // 不等, 则重置pos
                if(key.charAt(pos)==key.charAt(i)){
                    pos++;
                    matchArr[i]=pos;
                }else{
                    pos=0;
                }
            }
            if(pos==0){
                // 如果pos=0,仅比较当前字符与首字符是否相等
                // 不等则什么都不做
                // 相等, 则pos++, 并将当前下标的匹配值设置1
                if(key.charAt(0)==key.charAt(i)){
                    pos++;
                    matchArr[i]=pos;
                }
            }
        }

        return matchArr;
    }

    /**
     * 获取关键字符串的权值
     * @param key
     * @return
     */
    public static int[] matchArr(String key){
        int[] matchArr=new int[key.length()];

        for(int i=0;i<key.length();i++){
            matchArr[i]=match(key,i+1);
        }

        return matchArr;
    }

    public static int match(String key,int len){
        if (len==1) {
            return 0;
        }
        int right=len-1;
        int pos;
        int maxMatch=0;
        boolean flag;
        while(right>0){
            // 当某个right对应的char恰好与首char一致时, 检测后续char是否与首char后续一致
            if(key.charAt(right)==key.charAt(0)){
                pos=0;
                flag=true;
                while(right+pos<len){
                    if (key.charAt(right+pos)!=key.charAt(pos)) {
                        flag=false;
                        break;
                    }
                    pos++;
                }
                if(flag){
                    maxMatch=pos;
                }
            }

            right--;
        }


        return maxMatch;
    }
}
